GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Graham Scan</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Graham Scan</h1>

</header>

</div>

Der Graham Scan (nach <a href="Ronald_Graham" title="Ronald Graham">Ronald Graham</a> 1972) ist ein effizienter <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur Berechnung der <a href="Konvexe_H%C3%BClle" title="Konvexe Hülle">konvexen Hülle</a> einer endlichen Menge von Punkten in der Ebene. Bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Punkten liegt seine <a href="Asymptotische_Laufzeit" class="mw-redirect" title="Asymptotische Laufzeit">asymptotische Laufzeit</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9aaa0e99aa50f586bff0578a16e55dffcd9d5bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.487ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Beschreibung">Beschreibung</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Vorbereitung">Vorbereitung</h3></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\{P\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\{P\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aaa7a66ff0e8ff25eed7e47b24368abb19a160a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.668ex; height:2.843ex;" alt="{\displaystyle S=\{P\}}" loading="lazy"> eine endliche Punktmenge. Der Algorithmus beginnt mit einem Punkt der Menge, welcher garantiert ein Eckpunkt der konvexen Hülle ist. Man sucht sich dazu den Punkt mit der kleinsten <a href="Ordinate" class="mw-redirect" title="Ordinate">Ordinate</a>. Sind dies mehrere, so sucht man sich aus diesen Punkten den mit der kleinsten <a href="Abszisse" class="mw-redirect" title="Abszisse">Abszisse</a> aus (<a href="Lexikographisch" class="mw-redirect" title="Lexikographisch">lexikographische</a> Suche). Diese Suche kann in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> Schritten durchgeführt werden. Nachdem der Startpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> gefunden wurde, sortiert der Algorithmus die restlichen Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> nach aufsteigendem Winkel zwischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> → <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> und der x-Achse gegen den Uhrzeigersinn. Haben dabei zwei Punkte den gleichen Winkel (d. h. liegen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> auf einer Linie, sind kollinear mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy">), so wird der Punkt, welcher näher an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> liegt, verworfen.

<div class="mw-heading mw-heading2"><h2 id="Hilfsfunktion">Hilfsfunktion</h2></div>

In der nachfolgenden Rechnung muss wiederholt entschieden werden, ob drei Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=(x_{A},y_{A})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=(x_{A},y_{A})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4d2071ed1b22b9b4fef8a6d7a47c13186bb553f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.083ex; height:2.843ex;" alt="{\displaystyle A=(x_{A},y_{A})}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=(x_{B},y_{B})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=(x_{B},y_{B})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d35f5a1ca10c30afbb0286c496a94bb8e5251b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.134ex; height:2.843ex;" alt="{\displaystyle B=(x_{B},y_{B})}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=(x_{C},y_{C})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=(x_{C},y_{C})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/64992045f933f91bd171ab366a0cd16a7dec6f92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.139ex; height:2.843ex;" alt="{\displaystyle C=(x_{C},y_{C})}" loading="lazy"> in der Ebene ein positiv orientiertes Dreieck bilden. Äquivalente Formulierungen dafür sind, dass der Streckenzug <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ABC}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ABC}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5e55b44cfd965fbdc7a328d5db8a35a619db0971.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.273ex; height:2.176ex;" alt="{\displaystyle ABC}" loading="lazy"> einen Knick nach links hat oder dass der Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> links der Strecke von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> bzw. der Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> rechts von der Strecke von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> liegt.

Diese Aufgabe kann man durch Bestimmen aller relevanten Winkel lösen, oder einfacher durch die Berechnung einer <a href="Determinante" title="Determinante">Determinante</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(A,B,C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(A,B,C)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d738fa333dfaa90cd0eafc4cc373912c0f802f5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.787ex; height:2.843ex;" alt="{\displaystyle T(A,B,C)}" loading="lazy">, diese liefert das gewünschte Ergebnis mit weniger Rechenaufwand (fünf Subtraktionen, zwei Multiplikationen) und genauer. Das Ergebnis bleibt für rationale Koordinaten im <a href="Rationale_Zahl" title="Rationale Zahl">rationalen Zahlenbereich</a>, welcher ohne Verlust von Genauigkeit im Computer abgebildet werden kann. Das Ergebnis wird über den folgenden Ausdruck berechnet.

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}T(A,B,C)&={\begin{vmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{vmatrix}}={\begin{vmatrix}1&x_{A}&y_{A}\\0&x_{B}-x_{A}&y_{B}-y_{A}\\0&x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}={\begin{vmatrix}x_{B}-x_{A}&y_{B}-y_{A}\\x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}\\&=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})\\&={\begin{cases}<0,&{\text{wenn }}C{\text{ ist rechts von }}{\overrightarrow {AB}}\\=0,&{\text{wenn }}C{\text{ ist auf }}{\overrightarrow {AB}}\\>0,&{\text{wenn }}C{\text{ ist links von }}{\overrightarrow {AB}}\end{cases}}\end{aligned}}}">

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<mtext> ist rechts von </mtext>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<mtext> ist links von </mtext>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}T(A,B,C)&={\begin{vmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{vmatrix}}={\begin{vmatrix}1&x_{A}&y_{A}\\0&x_{B}-x_{A}&y_{B}-y_{A}\\0&x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}={\begin{vmatrix}x_{B}-x_{A}&y_{B}-y_{A}\\x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}\\&=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})\\&={\begin{cases}<0,&{\text{wenn }}C{\text{ ist rechts von }}{\overrightarrow {AB}}\\=0,&{\text{wenn }}C{\text{ ist auf }}{\overrightarrow {AB}}\\>0,&{\text{wenn }}C{\text{ ist links von }}{\overrightarrow {AB}}\end{cases}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/485043e1b143c48a357fad0500a5314aed5aad2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -11.63ex; margin-bottom: -0.208ex; width:79.36ex; height:24.843ex;" alt="{\displaystyle {\begin{aligned}T(A,B,C)&={\begin{vmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{vmatrix}}={\begin{vmatrix}1&x_{A}&y_{A}\\0&x_{B}-x_{A}&y_{B}-y_{A}\\0&x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}={\begin{vmatrix}x_{B}-x_{A}&y_{B}-y_{A}\\x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}\\&=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})\\&={\begin{cases}<0,&{\text{wenn }}C{\text{ ist rechts von }}{\overrightarrow {AB}}\\=0,&{\text{wenn }}C{\text{ ist auf }}{\overrightarrow {AB}}\\>0,&{\text{wenn }}C{\text{ ist links von }}{\overrightarrow {AB}}\end{cases}}\end{aligned}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Berechnung">Berechnung</h3></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> sei nun die sortierte Punktmenge. Als Nächstes läuft man alle Punkte in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> durch und prüft, ob diese Eckpunkte der konvexen Hülle sind. Es wird ein <a href="Stapelspeicher" title="Stapelspeicher">Stapelspeicher</a> (Stack) angelegt, auf welchem sich alle Eckpunkte der konvexen Hülle für alle bereits abgearbeiteten Punkte befinden. Zu Beginn liegen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy"> auf dem Stapel. Im <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-ten Schritt wird <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> zur Betrachtung herangezogen und berechnet, wie er die vorherige konvexe Hülle verändert. Aufgrund der Sortierung liegt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> immer außerhalb der Hülle der vorherigen Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i<k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i<k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d08208b704182ea0ce557056de9ad0530a5c1a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.112ex; height:2.176ex;" alt="{\displaystyle i<k}" loading="lazy">.

Durch das Hinzufügen des Punktes kann es vorkommen, dass bereits auf dem Stapel liegende Punkte nicht mehr zur neuen konvexen Hülle gehören. Diese Punkte müssen mittels der „pop“ Operation vom Stapel entfernt werden. Ob ein Punkt noch zur konvexen Hülle gehört oder nicht ermittelt man, indem man berechnet, ob <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> links oder rechts des Vektors PT2→PT1 liegt (PT1 = oberstes Element des Stapels, PT2 = Element direkt unter PT1). Liegt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> links, so bleibt PT1 weiterhin auf dem Stapel und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> wird mit „push“ auf dem Stapel abgelegt, liegt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> rechts, so wird PT1 von der neuen konvexen Hülle verschluckt, vom Stapel entfernt und die nächsten beiden oberen Punkte untersucht.

Dieser Test wird solange durchgeführt, bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> links des <a href="Vektor" title="Vektor">Vektors</a> PT2→PT1 oder nur noch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> und ein weiterer Punkt auf dem Stapel liegt. In beiden Fällen wird dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> auf dem Stapel abgelegt und mit dem nächsten Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d4b9c1fd5518e07786a205ecd70309683caf6226.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.682ex; height:2.509ex;" alt="{\displaystyle P_{k+1}}" loading="lazy"> weitergerechnet. Die folgende Abbildung zeigt ein Beispiel, in welchem alle Fälle des eben beschriebenen Tests auftreten.

In nebenstehender Abbildung werden zunächst die Punkte Pt4, Pt3, Pt2 und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ad1c5908a33e2947bba5d1163d356532ad9d9d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.682ex; height:2.509ex;" alt="{\displaystyle P_{k-1}}" loading="lazy"> auf den Stack gelegt. Zu jedem Zeitpunkt bilden die Punkte auf dem Stack ein konvexes Polygon (gestrichelte Linien). Erst als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> hinzukommen soll, fallen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ad1c5908a33e2947bba5d1163d356532ad9d9d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.682ex; height:2.509ex;" alt="{\displaystyle P_{k-1}}" loading="lazy"> und Pt2 wieder raus, da sie zusammen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> nicht konvex sind. Die konvexe Hülle dieser Punktmenge besteht aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy">, Pt4, Pt3 und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> liegt dabei auf dem Stack ganz unten und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c7bb3bc49771af415744e5dd40f5f93d14f5519.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle P_{k}}" loading="lazy"> ganz oben. Die Punkte des gesuchten konvexen Polygons können mit „pop“ im Uhrzeigersinn vom Stapel geholt werden.

<div class="mw-heading mw-heading3"><h3 id="Anmerkung">Anmerkung</h3></div>

Die Anzahl der „push“ und „pop“ Operationen übersteigt die obere Grenze von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/134afa8ff09fdddd24b06f289e92e3a045092bd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.557ex; height:2.176ex;" alt="{\displaystyle 2n}" loading="lazy"> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> = Anzahl der Punkte in der Eingabemenge) nicht. Die Berechnung ist also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy">. Die Sortierung der Punkte nach Winkel kann mit jedem beliebigen Sortieralgorithmus durchgeführt werden, z. B. <a href="Mergesort" title="Mergesort">Mergesort</a>. Dieser hat eine asymptotische <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Laufzeit</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9981ede263cbf28215d3a70bf30f55db41a6e692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.195ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log n)}" loading="lazy">. Das bedeutet, dass die Laufzeit des Algorithmus durch die Sortierung vorgegeben ist, da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)+{\mathcal {O}}(n\log n)={\mathcal {O}}(n\log n)}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)+{\mathcal {O}}(n\log n)={\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8365f7806bfbcc3c0a9184ff8591f559fa3be76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.382ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)+{\mathcal {O}}(n\log n)={\mathcal {O}}(n\log n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Unter_Nutzung_eines_Stacks">Unter Nutzung eines Stacks</h3></div>

<pre>Funktion GrahamScan

Eingabe: Punktemenge S = {P}

Ausgabe: konvexe Hülle von S

Beginn Funktion

Sei S die nach dem Winkel zu P0 sortierte Punktemenge

PUSH(P0)

PUSH(P1)

i := 2

n := Anzahl der Punkte in S

Solange i < n, führe aus:

Sei Pt1 der oberste Punkt auf dem Stack

Sei Pt2 der zweitoberste Punkt auf dem Stack

Wenn Si links des Vektors Pt2→Pt1 liegt oder Stack enthält 2 Elemente, dann führe aus:

PUSH(Si)

i := i + 1

Ansonsten führe aus:

POP(Pt1)

Ende Bedingung

Ende Schleife

Ende Funktion

</pre>

<div class="mw-heading mw-heading3"><h3 id="Ohne_Nutzung_eines_Stacks">Ohne Nutzung eines Stacks</h3></div>

<pre>Funktion GrahamScan

Eingabe: Punktemenge S = {P}

Ausgabe: konvexe Hülle von S

Beginn Funktion

Sei S die nach dem Winkel zu P0 sortierte Punktemenge

i := 1

Solange i ≤ |S|:

Wenn Si rechts des Vektors Si−1→Si+1 liegt, dann führe aus:

i := i + 1

Ansonsten führe aus:

Entferne das Element Si aus S

i := i - 1

Ende Bedingung

Ende Schleife

Ende Funktion

</pre>

Im Code sei <code>punkte</code> ein <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> aus Punkten, aus dem man mit <code>punkte[i]</code> das <code>i</code>-te Element erhält und welches schon nach dem Winkel zu <code>punkte[0]</code> sortiert ist. Der Code verändert dieses Array, indem die Elemente gelöscht werden, die nicht zur konvexen Hülle gehören.

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a> zeigt die Implementierung des Graham Scan Algorithmus. Die Punkte und die <a href="Konvexe_H%C3%BClle" title="Konvexe Hülle">konvexe Hülle</a> werden auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere <a href="Klasse_(Objektorientierung)" title="Klasse (Objektorientierung)">Klassen</a>. Die <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methoden</a> für den eigentlichen Algorithmus werden in der Klasse GrahamScan deklariert.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

<td style="text-align:left; font-size: 95%;">Code-Schnipsel

</td></tr>

<tr>

<td>

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>using System;

using System.Collections.Generic;

using System.Drawing;

using System.Windows.Forms;

// Klasse, die die Methoden für den Algorithmus Graham Scan deklariert

class GrahamScan

{

// Diese Methode gibt das zweitoberste Element im Stack der Punkte zurück

private PointF GetNextToTopElement(Stack<PointF> points)

{

PointF topElement = points.Peek();

points.Pop();

PointF nextToTopElement = points.Peek();

points.Push(topElement);

return nextToTopElement;

}

// Diese Methode gibt den Abstand der zwei Punkte zurück

private float GetDistance(PointF point1, PointF point2)

{

return (point1.X - point2.X) * (point1.X - point2.X) + (point1.Y - point2.Y) * (point1.Y - point2.Y);

}

// Diese Methode bestimmt die Orientierung des drei Punkte. Wenn die Punkte im Uhrzeigersinn sind, wird der Wert 1 zurückgegeben. Wenn die Punkte im Gegenuhrzeigersinn sind, wird der Wert -1 zurückgegeben. Wenn die Punkte kollinear sind, wird der Wert 0 zurückgegeben.

private int GetOrientation(PointF point1, PointF point2, PointF point3)

{

float area = (point2.Y - point1.Y) * (point3.X - point2.X) - (point2.X - point1.X) * (point3.Y - point2.Y);

if (area > 0) // Wenn das Vorzeichen positiv ist, sind die Punkte im Uhrzeigersinn

{

return 1;

}

if (area < 0) // Wenn das Vorzeichen negativ ist, sind die Punkte im Gegenuhrzeigersinn

{

return -1;

}

return 0; // Wenn der Flächeninhalt gleich 0 ist, sind die Punkte kollinear

}

// Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der Punkte

class PointComparer : Comparer<PointF>

{

public PointF center;

public GrahamScan grahamScan;

// Vergleichsmethode, die die Punkte in Bezug auf den Punkt center sortiert

public override int Compare(PointF point1, PointF point2)

{

int orientation = grahamScan.GetOrientation(center, point1, point2);

if (orientation == 0)

{

if (grahamScan.GetDistance(center, point2) >= grahamScan.GetDistance(center, point1))

{

return -1;

}

return 1;

}

return orientation;

}

// Diese Methode gibt eine Liste der Punkte der konvexen Hülle zurück

public List<PointF> GetConvexHull(List<PointF> points)

{

List<PointF> convexHull = new List<PointF>(); // Initialisiert die Liste der Punkte der konvexen Hülle

float minimumY = points[0].Y;

int indexOfMinimum = 0;

int numberOfpoints = points.Count;

// Diese for-Schleife durchläuft die verbleibenden Punkte und ermittelt den untersten Punkt und bei Gleichheit den Punkt ganz links

for (int i = 1; i < numberOfpoints; i++)

{

float y = points[i].Y;

if (y < minimumY || minimumY == y && points[i].X < points[indexOfMinimum].X)

{

minimumY = points[i].Y;

indexOfMinimum = i;

}

// Setzt den untersten Punkt an die erste Position

PointF point = points[0];

points[0] = points[indexOfMinimum];

points[indexOfMinimum] = point;

// Initialisiert das Objekt, das die Vergleichsmethode bereitstellt

PointComparer pointComparer = new PointComparer();

pointComparer.center = points[0];

pointComparer.grahamScan = this;

points.Sort(pointComparer); // Sortiert die Punkte in Bezug auf den ersten Punkt

// Wenn zwei oder mehr Punkte den gleichen Winkel mit dem Punkt point bilden, werden alle entfernt außer dem Punkt, der am weitesten vom Punkt point entfernt ist

int index = 1;

for (int i = 1; i < numberOfpoints; i++)

{

// Entfernt jeweils das Element mit Index i, solange die Punkte der gegebenen Elemente kollinear sind

while (i < numberOfpoints - 1 && GetOrientation(pointComparer.center, points[i], points[i + 1]) == 0)

{

i++;

}

points[index] = points[i];

index++;

}

if (index < 3) // Wenn weniger als 3 Punkte vorhanden sind, wird eine leere Liste zurückgegeben

{

return convexHull;

}

// Erzeugt einen Stack und fügt die ersten 3 Punkte hinzu

Stack<PointF> pointStack = new Stack<PointF>();

pointStack.Push(points[0]);

pointStack.Push(points[1]);

pointStack.Push(points[2]);

// Diese for-Schleife durchläuft die verbleibenden Punkte

for (int i = 3; i < index; i++)

{

// Entfernt jeweils das oberste Element des Stack, solange die Punkte der gegebenen Elemente im Uhrzeigersinn sind

while (pointStack.Count > 1 && GetOrientation(GetNextToTopElement(pointStack), pointStack.Peek(), points[i]) != -1)

{

pointStack.Pop();

}

pointStack.Push(points[i]);

}

// Fügt die Punkte des Stack der Liste der Punkte der konvexen Hülle hinzu

while (pointStack.Count != 0)

{

convexHull.Add(pointStack.Peek());

pointStack.Pop();

}

return convexHull;

}

}

// Klasse für das Hauptfenster

public partial class MainForm : Form

{

private Graphics graphics;

private List<PointF> points = new List<PointF>(); // Liste der Punkte

private List<PointF> convexHull = new List<PointF>(); // Liste der Punkte der konvexen Hülle

private double x1, y1, x2, y2;

public MainForm()

{

x1 = 100; y1 = 100; x2 = 700; y2 = 700; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche

Random random = new Random(); // Initialisiert den Zufallsgenerator

int numberOfPoints = 100;

for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 100 zufällige Punkte innerhalb der quadratischen Zeichenfläche

{

PointF point = new PointF();

point.X = (float)(random.NextDouble() * (x2 - x1) + x1);

point.Y = (float)(random.NextDouble() * (y2 - y1) + y1);

points.Add(point); // Fügt den Punkt der Liste hinzu

}

GrahamScan grahamScan = new GrahamScan(); // Erzeugt ein Objekt der Klasse GrahamScan

convexHull = grahamScan.GetConvexHull(points); // Aufruf der Methode, die die konvexe Hülle zurückgibt

InitializeComponent();

Text = "Konvexe Hülle";

Width = 800;

Height = 800;

graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster.

Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.

}

// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird.

private void OnPaint(object sender, PaintEventArgs e)

{

for (int i = 0; i < points.Count; i++)

{

graphics.FillRectangle(new SolidBrush(Color.FromArgb(0, 0, 0)), points[i].X - 1, points[i].Y - 1, 2, 2); // Zeichnet die Punkte

}

int numberOfPoints = convexHull.Count;

for (int i = 0; i < numberOfPoints; i++)

{

graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), convexHull[i], convexHull[(i + 1) % numberOfPoints]); // Zeichnet die Kanten der konvexen Hülle

}

}

</pre></div>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.informatik.uni-trier.de/~naeher/Professur/PROJECTS/grahams_scan/index.htm">Erklärungen samt Visualisierung des Verfahrens</a></li>

<li><a rel="nofollow" class="external text" href="http://cs.smith.edu/~jorourke/books/compgeom.html">Computational Geometry in C (Second Edition)</a></li>

<li><a rel="nofollow" class="external text" href="http://www.iti.fh-flensburg.de/lang/algorithmen/geo/graham.htm">Erklärung und Pseudocode</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/njanakiev/graham-scan">Animation des Graham Scan Algorithmus</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Rosetta Code: <a rel="nofollow" class="external text" href="https://rosettacode.org/wiki/Convex_hull">Convex hull</a>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/">Convex Hull</a>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-11-14" href="https://de.wikipedia.org/wiki/?title=Graham_Scan&oldid=261550695">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>